# 780 困难：到达终点

# def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
# def reachingPoints(sx, sy, tx, ty):
#     if sx == tx and sy == ty:
#         return True
#
#     if tx == 0 or ty == 0:
#         return False
#
#     if tx > ty:
#         return reachingPoints(sx, sy, tx - ty, ty)
#     else:
#         return reachingPoints(sx, sy, tx, ty - tx)

class Solution:
    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
        while sx < tx != ty > sy:
            if tx > ty:
                tx %= ty
            else:
                ty %= tx
        if tx == sx and ty == sy:
            return True
        elif tx == sx:
            return ty > sy and (ty - sy) % tx == 0
        elif ty == sy:
            return tx > sx and (tx - sx) % ty == 0
        else:
            return False


s = Solution()
print(s.reachingPoints(1, 1, 1000000, 1))
